import java.util.*;

// https://leetcode.cn/problems/subsets-ii/
public class SubSet2 {
    class Solution {
        private List<List<Integer>> res = new ArrayList<>();
        public List<List<Integer>> subsetsWithDup(int[] nums) {
            Arrays.sort(nums);
            backTracking(new ArrayList<>(),0,nums);
            return res;


        }

        private void backTracking(List<Integer> path , int start, int[] nums)
        {

           
            res.add(new ArrayList<>(path));
            for(int i = start ; i < nums.length ; i ++)
            {
                if(i > start && nums[i] == nums[i-1]) continue;
                path.add(nums[i]);
                backTracking(path,i+1,nums);
                path.remove(path.size()-1);
            }

        }
    }
}
